﻿using System;
namespace CourseExamples
{
    public class C03_Brute_Force
    {
        public C03_Brute_Force()
        {

        }

        public void Run()
        { 
            for (int i = 0; i < 5; i++)
            {
                Console.WriteLine("---------------");
                test3(30);
                Console.WriteLine();
            }
            
        }

        public void test1()
        {
            var arr = new int[] { 1, 2, 5, 3, 6 };

            // a hidden condition: arr.Length + 1 == max number
            int max = arr.Length + 1; // numbers: 1, 2, ..., N

            arr = arr.OrderBy(n => n).ToArray();

            for (int i = 0; i < arr.Length; i++)
                Console.WriteLine(arr[i]);


            for (int i = 0; i < arr.Length + 1; i++)
            {
                if (i + 1 != arr[i])
                {
                    Console.WriteLine((i + 1) + " is the missing number.");
                    break;
                }
            }
        }

        static Random rand = new Random();
        public void test2(int N = 30)
        {
            var list = new List<int>();
            for (int i = 0; i < N; i++)
                list.Add(i + 1);
            print("original", list);

            shuffle(list);
            print("shuffled", list);

            int pos = rand.Next(N);
            // pos = N - 1;
            list.RemoveAt(pos);
            print("removed", list);

            list = list.OrderBy(n => n).ToList();
            print("ordered", list);

            int mid = 0;
            for(int i = 0; i < N - 1; i++)
            {
                if(i + 1 != list[i])
                {
                    mid = i;
                    break;
                }
            }

            if (mid == 0)
                mid = N - 1;
            Console.WriteLine((mid + 1) + " is the missing number.");
        }

        public void test3(int N = 5)
        {
            var list = new List<int>();
            for (int i = 0; i < N; i++)
                list.Add(i + 1);
            print("original", list);

            shuffle(list);
            print("shuffled", list);

            int pos = rand.Next(N);
            // pos = N - 1;
            list.RemoveAt(pos);
            print("removed", list);


            int[] arr = new int[N + 1];
            for (int i = 0; i < list.Count; i++)
                arr[list[i]] = 1;

            for (int i = 1; i <= N; i++)
                if (arr[i] == 0)
                    Console.WriteLine(i + " is the missing number.");
    
        }

        public static void shuffle(List<int> list)
        {
            for (int i = 0; i < list.Count; i++)
            {
                int pos = rand.Next(list.Count);
                int temp = list[pos];
                list[pos] = list[i];
                list[i] = temp;
            }
        }

        public static void print(List<int> list)
        {
            Console.WriteLine("[" + String.Join(",", list) + "]");
        }

        public static void print(String title, List<int> list)
        {
            Console.WriteLine(title + ":  \t[" + String.Join(",", list) + "]");
        }




    }
}

